package com.mybatis.common;

import com.alibaba.fastjson.JSONObject;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author liuxiaoding
 * @Date 2021/7/30
 * 二叉树
 **/
public class BinaryTree {
    private static TreeNode rootNode;

    /**
     * 新增节点
     * @param currentNode
     * 二叉树左侧节点小于右侧节点
     * @param value
     * @return
     */
    public static TreeNode addNode(TreeNode currentNode, int value){
        if(currentNode == null){
            return new TreeNode(value,null,null);
        }
        if(currentNode.value<value){
            currentNode.rightNode=addNode(currentNode.rightNode,value);
        }
        if(currentNode.value>value){
            currentNode.leftNode=addNode(currentNode.leftNode,value);
        }
        return currentNode;
    }

    /**
     * 获取节点最小值
     * @param currentNode
     * @return
     */
    public static int getLeftNodeValue(TreeNode currentNode){
        if(currentNode.leftNode != null){
            return getLeftNodeValue(currentNode.leftNode);
        }
        return currentNode.getValue();
    }

    public static TreeNode deleteNode(TreeNode treeNode,int value){
         if(treeNode==null){

         }
         if(treeNode.value==value){
             if(treeNode.leftNode==null&&treeNode.rightNode==null){
                 return null;
             }
             if(treeNode.leftNode!=null){
                 return treeNode.leftNode;
             }
             if(treeNode.rightNode!=null){
                 return treeNode.rightNode;
             }
             //获取右侧节点最小值
             int minValue=getLeftNodeValue(treeNode.rightNode);
             //替换
             treeNode.setValue(minValue);
             treeNode.rightNode=deleteNode(treeNode.rightNode,minValue);
         }
         if(treeNode.value<value){
             treeNode.rightNode=deleteNode(treeNode.rightNode,value);
         }
         if(treeNode.value>value){
             treeNode.leftNode=deleteNode(treeNode.leftNode,value);
         }
         return treeNode;
    }

    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left=node.leftNode;
            node.leftNode = node.rightNode;
            node.rightNode = left;
            if (node.leftNode != null) {
                queue.offer(node.leftNode);
            }
            if (node.rightNode != null) {
                queue.offer(node.rightNode);
            }
        }
        return root;
    }

    public static TreeNode invertTree1(TreeNode rootNode){
        if(rootNode==null){
            return null;

        }
        TreeNode left=rootNode.leftNode;
        rootNode.leftNode = rootNode.rightNode;
        rootNode.rightNode = left;
        invertTree1(rootNode.leftNode);
        invertTree1(rootNode.rightNode);
        return rootNode;
    }

    public static void main(String[] args) {
        rootNode = addNode(rootNode,1);
        rootNode = addNode(rootNode,9);
        rootNode = addNode(rootNode,3);
        rootNode = addNode(rootNode,5);
        rootNode = addNode(rootNode,3);
        rootNode = addNode(rootNode,6);
        rootNode = addNode(rootNode,9);
        rootNode = addNode(rootNode,2);
        System.out.println("最小值："+getLeftNodeValue(rootNode));
        System.out.println(JSONObject.toJSONString(rootNode));
        rootNode=deleteNode(rootNode,1);
        System.out.println(JSONObject.toJSONString(rootNode));
        rootNode=invertTree1(rootNode);
        System.out.println(JSONObject.toJSONString(rootNode));
    }
}
